package 算法.回溯;

import java.util.Arrays;

public class JZ12矩阵中的路径 {
    //递归与回溯
    public boolean hasPath (char[][] matrix, String word) {
        //优先处理特殊情况
        if(matrix.length == 0)
            return false;
        int n = matrix.length;
        int m = matrix[0].length;
        //初始化flag矩阵记录是否走过
        boolean[][] flag = new boolean[n][m];
        //遍历矩阵找起点
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                //通过dfs找到路径
                if(dfs(matrix, n, m, i, j, word, 0, flag))
                    return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] matrix, int n, int m, int i, int j, String word, int k, boolean[][] flag){
        if(i < 0 || i >= n || j < 0 || j >= m || (matrix[i][j] != word.charAt(k)) || (flag[i][j] == true))
            //下标越界、字符不匹配、已经遍历过不能重复
            return false;
        //k为记录当前第几个字符
        if(k == word.length() - 1)
            return true;
        flag[i][j] = true;
        //该结点任意方向可行就可
        if(dfs(matrix, n, m, i - 1, j, word, k + 1, flag)
                ||dfs(matrix, n, m, i + 1, j, word, k + 1, flag)
                ||dfs(matrix, n, m, i, j - 1, word, k + 1, flag)
                ||dfs(matrix, n, m, i , j + 1, word, k + 1, flag))
            return true;
        //没找到经过此格的，此格未被占用
        flag[i][j] = false;
        return false;
    }
}
